home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7678 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.5 KB  |  121 lines
  1. Path: isonews.bbn.hp.com!hpbblb!news
  2. From: Matthias Dittrich <matti>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Permutations
  5. Date: 26 Feb 1996 09:51:07 GMT
  6. Organization: Hewlett-Packard Co.
  7. Message-ID: <4grvqb$8n9@hpbblb.bbn.hp.com>
  8. References: <Dn8yz9.GGy@spuddy.mew.co.uk>
  9. NNTP-Posting-Host: trabant.bbn.hp.com
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 1.1N (X11; I; HP-UX A.09.07 9000/712)
  14. X-URL: news:Dn8yz9.GGy@spuddy.mew.co.uk
  15.  
  16. david@spuddy.mew.co.uk (David Turner) wrote:
  17. >Does anyone know of an algorithm that works out the different purmutations
  18. >of ordering a number of objects? Not calculating how many there are, but 
  19. >actaully working out (quickly?) what they permutations are!
  20. > 
  21. >        eg. permutations of objects A, B and C:
  22. > 
  23. >                A B C   B A C   C A B
  24. >                A C B   B C A   C B A
  25. > 
  26. >Any help would be greatly appreciated.
  27. > 
  28. >David
  29. > 
  30. Here is one I've just written:
  31.  
  32. #include <stdio.h>
  33. #include <string.h>
  34.  
  35. #define MAX_PERM 8
  36.  
  37. void permfunc(unsigned long i, char* str);
  38. void do_perm(char* str);
  39.  
  40. int main(int argc, char** argv)
  41. {
  42.   unsigned long n = 2, i;
  43.   char str[MAX_PERM];
  44.  
  45.     /* do some essential checks */
  46.   if(argc < 2) return 1;
  47.  
  48.   sscanf(argv[1], "%lu", &n);
  49.  
  50.   if(n >= MAX_PERM)
  51.   {
  52.     n = MAX_PERM - 1;
  53.     fprintf(stderr, "number too big, set to %d\n", n);
  54.   }
  55.  
  56.     /* initialize the string to show permutations */
  57.   for(i=0; i<n; i++)
  58.   {
  59.     str[i] = 'A' + i;
  60.   }
  61.   str[n] = '\0';
  62.  
  63.     /* call permfunc with starting level 0 */
  64.   permfunc(0, str);
  65.  
  66.   return 0;
  67. }
  68.  
  69. void permfunc(unsigned long i, char* str)
  70. {
  71.   char s[MAX_PERM];
  72.   char *t = s + i;
  73.   char *u = str + i;
  74.  
  75.     /* check if at least two characters are in the string */
  76.   if(*u && *(u + 1))
  77.   {
  78.     strcpy(s, str);
  79.  
  80.     permfunc(i + 1, s);
  81.     u = t + 1;
  82.  
  83.       /* the number of characters in the string is the number of
  84.          permutations to do */
  85.     while(*u)
  86.     {
  87.         /* after the permutation has been done
  88.            call this function recursively, increasing the starting level */
  89.       do_perm(t);
  90.       permfunc(i + 1, s);
  91.       u++;
  92.     }
  93.   }
  94.   else
  95.   {
  96.     printf("%s\n", str);
  97.   }
  98. }
  99.  
  100.   /* do the permutation on a string */
  101. void do_perm(char* str)
  102. {
  103.   char *s, *t, c;
  104.  
  105.   s = t = str;
  106.   t++;
  107.  
  108.     /* save first char */
  109.   c = *s;
  110.     /* move all chars one position to the left */
  111.   while(*t) *s++ = *t++;
  112.     /* set the last char */
  113.   *s = c;
  114. }
  115.  
  116. I think there may be faster ways to do it, but it works.
  117.  
  118. Good luck,
  119. Matthias
  120.  
  121.